class Solution {
public:
    bool dfs(int* mark,int x,vector<vector<int>>& g)
    {
        //现在要访问x的邻边节点
        mark[x] = 1;//x正在访问中
        for(int e:g[x])
        {
            if(mark[e] == 1||mark[e] == 0&&dfs(mark,e,g))
            {
                return true;//如果e这个点正在被访问中，或者这个点没有访问过，但是这个节点再访问的时候存在了环
            }
        }
        mark[x] = 2;//这个节点访问完毕了,并且不存在环
        return false;//这个点不存在环
    }
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) 
    {
        // 这道题目就是让我们在一个图中判断是否存在环，比如说 [1 2] [2 3]，此时的图关系为3->2->1此时是没有环的
        // 那么我也能完成课程的选修，但是如果是[1 2] [2 3] [2 1]3->2<->1出现了环，那么我也不能选修完成
        // 当然我的这个例子有些简单，但是大概意思就是这样，如何解题呢？首先要建图，然后再使用一个数组进行标记
        // 标记的值为3种分别代表 0 代表整个节点没有被访问过，1代表这个节点已经被访问过，但是没有返回值
        // 2代表这个节点已经被访问过，并且已经返回值了，然后我们可以递归遍历图中的节点，将这个节点的状态修改为1如果再遍历，某一个节点的时候
        // 发现他的邻节点正在访问并且没有返回代表存在了环，返回true，如果邻节点的状态为没有访问过就去访问这个节点
        // 如果发现这个节点的状态为2，代表这个节点访问完成了并且不存在环，我这里返回false，最后的答案
        // 就是存在环返回flase。不存在返回true
        // 首先要建图
        vector<vector<int>> g(numCourses);
        for(auto&e:prerequisites)
        {
            g[e[1]].push_back(e[0]);
            //0:1
        }
        int mark[numCourses];
        memset(mark,0,sizeof(mark));
        //开始遍历节点中的值
        for(int i = 0;i<numCourses;i++)
        {
            if(mark[i] == 0&&dfs(mark,i,g))
            {
                return false;//出现了环
            }
        }
        return true;//没有出现环
    }
};